1. Field of the Invention
The present invention relates generally to user programmable integrated circuit devices and, in particular, to the provision of both local and express diagonal busses in a configurable logic array.
2. Discussion of the Prior Art
A configurable logic array (CLA) is a matrix of interconnected, programmable logic cells. The individual logic function and the active inputs and outputs of each logic cell are determined by parameter flip-flops and logic gates within the cell, rather than by physically customizing the array during manufacture. Thus, the individual cell functions and the interconnections between cells are dynamically programmable to provide a wide variety of functions. The greater the number of cells in the array, the greater the functional flexibility of the CLA device.
The configurable logic array concept was first introduced by Sven E. Wahlstrom in 1967. Wahlstrom, Electronics, Dec. 11, 1967, pp. 90-95.
Since then, Xilinx Inc., Actel Inc., Pilkington Micro-electronics Ltd. and Concurrent Logic, Inc., among others, have proposed implementations of CLA devices.
The basic Xilinx CLA architecture is disclosed in U.S. Pat. No. 4,870,302, which issued to Ross H. Freeman on Feb. 19, 1988.
The CLA device described by the Xilinx '302 patent and shown in FIG. 1 includes an array of configurable logic elements that are variably interconnected in response to control signals to perform selected overall logic functions. Each configurable element in the array is capable of performing a number of logic functions depending upon the control information provided to that element. The array can have its function varied at any time by changing its control information.
FIG. 2 shows a CLA interconnect structure currently utilized in the Xilinx array. In addition to the single-length interconnect lines between logic elements, as shown in FIG. 2, the Xilinx array utilizes lines that connect switch matrices, e.g., two vertical and two horizontal double-length lines per logic-element column. The Xilinx array also utilizes "global" interconnect lines, e.g., six vertical global lines and six horizontal globe lines per logic-element column, for clocks, resets and other global signals. Two of the horizontal global lines may be placed in a high impedance state.
FIG. 3 shows a logic-element currently utilized in the Xilinx array. The Xilinx logic element has three function generators, two flip-flops, and several multiplexers. The first two function generators can perform a Boolean function of four inputs. The function generators are implemented as memory look-up tables. The outputs of these two function generators are provided to the multiplexers and to a three-input function generator which can perform a Boolean function of G', F', and an external input. The output of the third function generator is also provided to the multiplexers. The multiplexers select whether the signals are provided to the output of the logic element or to the input of the flip-flops. The flip-flops have common clock, enable, and set or reset inputs. The configuration bits that determine the function of the logic element also determine how the C1 through C4 inputs are mapped into the four inputs: H1, DIN, S/R, and EC.
The basic Pilkington CLA architecture is disclosed in U.S. Pat. No. 4,935,734, which issued to Kenneth Austin on Sept. 10, 1986.
An implementation of the CLA architecture disclosed in the Pilkington '734 patent is shown in FIG. 4. Each logic element in the Pilkington array accepts inputs from four other logic elements in the illustrated pattern. Each logic element output drives multiple other elements as illustrated. In the '734 patent there is no additional wiring. However, the Plessey Company, under license from Pilkington, has marketed a product wherein bus wiring is added as shown in FIG. 4; i.e. in every third column, a bus provides inputs to every right-direction logic element in that column, and every third row has a bus providing inputs to every left-direction logic element in that row.
FIG. 5 shows a logic cell currently utilized in the FIG. 4 array. As shown in FIG. 5, each of the two inputs to a NAND gate are provided by a user configured multiplexer the inputs of which are provided by other logic elements or inputs. Plessey has also added circuitry to the logic element to permit it to be a latch or a 2-input NAND gate.
The basic Actel CLA architecture is disclosed in U.S. Pat. No. 4,873,459, issued to El Gamal et al on Oct. 10, 1989.
The Actel architecture relies on one-time programmable anti-fuses for configurability and, thus, is not re-programmable.
The Concurrent Logic, Inc. (CLI) CLA architecture, which is most relevant to the present invention, is discussed below in conjunction with FIGS. 6-17. Features of the CLI CLA architecture are disclosed in the following U.S. patents issued to Frederick C. Furtek: U.S. Pat. No. 4,700,187, issued Oct. 13, 1987; U.S. Pat. No. 4,918,440, issued Apr. 17, 1990; and U.S. Pat. No. 5,019,736, issued May 28, 1991.
As discussed in above-cited related application Ser. No. 07/608,415, a CLA may be viewed as an array of programmable logic on which a flexible bussing network is superimposed. As shown in FIG. 6, the heart of the CLI CLA 10 is a two-dimensional array of logic cells 12 each of which receives inputs from and provides outputs to its four adjacent neighbors. The core logic cell 12, which is shown in detail in FIG. 7, can be programmed to provide all the wiring and logic functions needed to create any digital circuit.
Each logic cell 12 in the array, other than those on the periphery, receives eight inputs from and provides eight outputs to its North (N), East (E), South (S), and West (W) neighbors. These sixteen inputs and outputs are divided into two types, "A" and "B", with an A input, an A output, a B input and a B output for each neighboring cell 12. Between cells 12, an A output is always connected to an A input and a B output is always connected to a B input.
As further shown in FIG. 7, within a cell 12, the four A inputs enter a user-configurable multiplexer 14, while the four B inputs enter a second user-configurable multiplexer 16. The two multiplexer outputs feed the logic components of the cell 12. In logic cell 12, these components include a NAND gate 18, a register 20, an XOR gate 22, and two additional user-configurable multiplexers 24 and 26.
The two four-input multiplexers 24 and 26 are controlled in tandem (unlike the input multiplexers), giving rise to four possible logic configurations, shown in FIGS. 8A-8D. In the FIG. 8A configuration, corresponding to the "0" inputs of the multiplexers 24 and 26, the A outputs are connected to a single A input and the B outputs are connected to a single B input.
In the FIG. 8B configuration, corresponding to the "1" inputs of the multiplexers 24 and 26, the A outputs are connected to a single B input and the B outputs are connected to a single A input.
In the FIG. 8C configuration, corresponding to the "2" inputs of the multiplexers 24 and 26, the A outputs provide the NAND and the B outputs the XOR of a single A input and a single B input. This is the equivalent of a half adder circuit.
In the FIG. 8D configuration, corresponding to the "3" inputs of the multiplexers 24 and 26, the Q output of edge-triggered D flip-flop 20 is connected to the A outputs, the D input of the flip-flop 20 is connected to a single A input, the enable (EN) input of the flip-flop 20 is connected to a single B input and the B outputs provide the logical constant "1". A global clock input and register reset are provided for this configuration, but is not illustrated in FIG. 8D. This configuration is equivalent to a one bit register.
The cell 12 thus provides the most fundamental routing and logic functions: extensive routing capabilities, NAND and XOR (half adder), a one-bit register, the logical constant "1" and fan-out capabilities.
These functions permit the basic CLA array 10 to implement arbitrary digital circuits. A register and half adder (NAND and XOR) included in each cell 12, together with a high cell density, make the array 10 well adapted for both register-intensive and combinatorial applications. In addition, signals passing through a cell 12 are always regenerated, ensuring regular and predictable timing.
Although the basic logic array 10 is completely regular, routing wires through individual cells 12 can cause increased delays over long distances. To address this issue, the neighboring interconnect provided by the array 10 is augmented with three types of programmable busses: local, turning, and express.
Local busses provide connections between the array of cells and the bussing network. They also provide the wired-AND function.
Turning busses provide for 90.degree. turns within the bussing network enabling T-intersections and corners. Turning busses provide faster connections than do local busses, since they do not have the delays associated with using a cell as a wire.
Express busses are designed purely for speed. They are the fastest way to cover straight-line distances.
There is one bus of each type described above for each row and each column of logic cells 12 in the array 10. Connective units, called repeaters, are spaced every eight cells 12 and divide each bus into segments spanning eight cells 12. Repeaters are aligned into rows and columns, thereby partitioning the basic array 10 into 8.times.8 blocks of cells 12 called "superblocks". FIG. 9 illustrates a simplified view of a bussing network containing four superblocks. Cell-to-cell connections are not shown.
As shown in FIG. 10, each local bus segment 13 is connected to eight consecutive cells 12. As shown in FIG. 11, each turning bus segment 15 is connected to eight orthogonal turning busses through programmable turn points. As shown in FIG. 12, each express bus segment 17 is connected only to the repeaters at either end of the 8.times.8 superblock. FIG. 13 shows the three types of busses combined to form the bussing network of the array 10.
In order for the bussing network to communicate with the array 10, each core logic cell 12 is augmented as shown in FIG. 14 to permit the reading and writing of local busses L. The cell 12 reads a horizontal local bus through the "L.sub.X " input of the B input multiplexer 16 and reads a vertical local bus through the "L.sub.Y " input of the B input multiplexer 16. The cell 12 writes to a local bus through the driver 28 connected to the A output.
While the cell 12 may read either a horizontal or a vertical bus under program control, the cell 12 may write to only one bus of fixed orientation. Whether a cell 12 writes to a horizontal or vertical bus is determined by its location with the array 10. Referring back to FIG. 10, the cell 12 in the upper-left corner of the illustrated superblock writes to a horizontal local bus. If a particular cell 12 writes to a horizontal local bus, then its four immediate neighbors write to vertical local busses, and vice versa.
As shown in FIG. 13, the two types of cells 12 are thus arranged in a checker-board pattern where the black cells 12 write to horizontal busses and the white cells 12 write to vertical busses.
The CLA busses can be driven by the bus driver 28 in two ways. The bus driver 28 has two control bits, "TS" and "OC", which provide high impedance and open-collector capabilities, respectively. The high impedance capability, which is independently programmable for each cell 12, allows the bus driver to be disconnected from the bus when the cell 12 is not being used to write to the bus.
The open-collector capability provides the wired-AND function when multiple cells 12 are driving the same local bus simultaneously. Unlike the high impedance function, which is controlled at the cell level, the open-collector function is controlled at the bus level; all cells 12 driving the same local bus are in the same open-collector state. The programming environment insures that if there is exactly one driver 28 driving a local bus, then that driver 28 provides active pull-up and active pull-down. (The open-collector capability is turned off.) In all other cases, the drivers 28 driving a local bus provide passive pull-up and active pull-down. (The open-collector capability is turned on.)
In the special case when there are no drivers 28 driving a local bus (that is, when the bus is not used), the open-collector capability is turned on and the bus is pulled high through the passive pull-up resistor. An unused local bus, therefore, provides a logical "1" to those cells reading the bus.
As stated above, repeaters provide connections between busses. Each repeater is programmable so that any bus on one side of a repeater can be connected to any bus on the other side of the repeater, as shown in FIG. 15. Each connection is unidirectional (direction is not depicted in FIG. 15) since repeaters always provide signal regeneration. The direction, like the connection itself, is programmable. Including direction, there are 18 (2.times.9) repeater configurations providing one connection, 72 (4.times.18) providing two connections, and 48 (8.times.6) providing three connections.
As shown in FIG. 16, logic 19 for distributing clock signals to the D flip-flops 20 in the logic cells 12 is located along one edge of the array 10. The distribution network is organized by column and permits columns of cells 12 to be independently clocked. At the head of each column is a user-configurable multiplexer 30 providing the clock signal for that column. There are four inputs to each multiplexer 30: an external clock supplied from off chip, the logical constant "0" the express bus adjacent to the distribution logic, and the A output of the cell 12 at the head of the corresponding column.
Through the global clock, the network provides low-skew distribution of an externally supplied clock to any or all of the columns of the array 10. The constant "0" is used to reduce power dissipation in columns containing no registers. The express bus is useful in distributing a secondary clock to multiple columns when the external clock line is used as a primary clock. The A output of a cell is useful in providing a clock signal to a single column.
All D flip-flops 20 of the cells 12 of the array 10 may be globally reset through an externally supplied signal entering the RESET control pin.
The CLA array 10 provides a flexible interface between the logic array, configuration control logic and the I/O pads of the CLA device. As shown in FIG. 17, two adjacent cells, an "exit" cell 12a and an "entrance" cell 12b, on the perimeter of the logic array are associated with each I/O pad 32. The A output of the exit cell 12a is connected, under program control, to an output buffer 34. The edge-facing A input of the adjacent entrance cell 12b is connected to an input buffer 36. The output of the output buffer 34 and the input to the input buffer 36 are both connected to the I/O pad 32. Control of the I/O logic is provided by various control signals and bits, as shown in FIG. 17.
While the CLA array 10 described above provides a wide range of configuration options, it would be desirable to have available a CLA device that provides an even greater level of programmable flexibility.